package nl.utwente.eemcs.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

import javax.activation.UnsupportedDataTypeException;

import br.ufscar.dc.graph.Abstraction;

/**
 * Graphs is a collection of nodes and edges
 * 
 * @author Evert Duipmans
 */
public class Graph implements Abstraction {

   /**
    * Attributes map of the graph
    */
   protected HashMap<String, Object> attributes = new HashMap<String, Object>();

   /**
    * List with the nodes of the graph
    */
   protected List<Node> nodes = new ArrayList<Node>();

   /**
    * List with the edges of the graph
    */
   protected List<Edge> edges = new ArrayList<Edge>();

   /**
    * The start node of the graph
    */
   protected Node startNode = null;

   /**
    * Add a node to the graph
    * 
    * @param node
    *           Node
    */
   public void addNode(Node node) {
      if (this.nodes.size() == 0)
         startNode = node;

      if (!this.nodes.contains(node)) {
         node.setParentGraph(this);
         this.nodes.add(node);
      }
   }

   
   public void addAllNodes(List<Node> nodes) {
      
      for(Node n : nodes) { 
         if (this.nodes.size() == 0)
            startNode = n;
   
         if (!this.nodes.contains(n)) {
            n.setParentGraph(this);
            this.nodes.add(n);
         }
      }
   }
   
   /**
    * Add an edge to the graph
    * 
    * @param edge
    *           Edge
    */
   public void addEdge(Edge edge) {
      if (!this.edges.contains(edge))
         this.edges.add(edge);
   }
   
   public void addAllEdges(List<Edge> edges) {
      for(Edge e : edges)
         if (!this.edges.contains(e))
            this.edges.add(e);
   }

   /**
    * Remove a node from the graph
    * 
    * @param node
    *           Node
    */
   public void removeNode(Node node) {
      this.nodes.remove(node);

      if (startNode == node)
         startNode = findStartNode();
   }

   /**
    * Remove an edge from the graph
    * 
    * @param edge
    */
   public void removeEdge(Edge edge) {
      this.edges.remove(edge);
   }

   /**
    * Get a node by its name
    * 
    * @param name
    *           Node name
    * @return The node with the given name, null otherwise
    */
   public Node getNodeByName(String name) {
      for (Node n : this.nodes) {
         if (n.getName().equals(name))
            return n;
      }
      return null;
   }

   public List<Node> getNodesByType(Class<?> cls) {
      List<Node> result = new ArrayList<Node>();
      for (Node n : nodes) {
         if (n.getClass() == cls)
            result.add(n);
      }
      return result;
   }

   /**
    * Method used to get a node into the graph by its name
    * 
    * <br/>
    * <br/>
    * <b>Modifications:</b><br/>
    * <blockquote>Support to copy on write behaviour. In the first version an
    * exception named ConcurrentModificationException being thrown when
    * ArrayList.addAll method was used.</blockquote>
    * 
    * @param name
    *           - The node name
    * @return A node with a specific name
    * @throws UnsupportedDataTypeException
    * 
    * @author Evert Duipmans
    * @author Lucas Venezian Povoa - modification from 15/11/2012
    * 
    */
   public Node getNodeByNameRecursively(String name)
         throws UnsupportedDataTypeException {

      Node result = null;
      
      for(Node n : this.nodes) {
         result = this.getNodeByNameRecursively(n, name);
         if (result != null) break;
      }
      
      return result;
   }
   
   private Node getNodeByNameRecursively(Node n, String name) throws UnsupportedDataTypeException {
      Node result = null;
      
      if(n.getName().equals(name))
         result =  n;
      else if (n instanceof CompositeNode<?, ?>)
         result = this.getNodeByNameRecursively((CompositeNode<?, ?>)n, name);
      
      return result;
   }

   private Node getNodeByNameRecursively(CompositeNode<?, ?> n, String name) throws UnsupportedDataTypeException {
      Node result = null;
      
      if (n.getName().equals(name))
         result = n;
      else if (n.getStartNode().getName().equals(name))
         result = n.getStartNode();
      else if (n.getEndNode().getName().equals(name))
         result = n.getEndNode();
      else if (n instanceof LoopConstruct)
         result = getNodeByNameRecursively((LoopConstruct)n, name);
      else if (n instanceof BranchedConstruct<?, ?>)
         result = getNodeByNameRecursively((BranchedConstruct<?, ?>)n, name);
      
      return result;
   }

   private Node getNodeByNameRecursively(LoopConstruct n, String name) throws UnsupportedDataTypeException {
      Node result = null;
      
      if (n.getConditionNode().getName().equals(name))
         result = n.getConditionNode();
      
      else for (Node cn : n.getInnerGraph().getNodes()) {
         result = getNodeByNameRecursively(cn, name);
         if (result != null) break;
      }
      
      return result;
   }
   
   private Node getNodeByNameRecursively(BranchedConstruct<?, ?> n, String name) throws UnsupportedDataTypeException {
      Node result = null;
      
      graphLoop:
      for (Graph g : n.getBranches())
         for (Node cn : g.getNodes()) {
            result = getNodeByNameRecursively(cn, name);
            if (result != null)
               break graphLoop;
         }
      
      return result;
   }

   /**
    * Get all nodes
    * 
    * @return List with nodes
    */
   public List<Node> getNodes() {
      return this.nodes;
   }

   /**
    * Get all nodes from a certain type
    * 
    * @param type
    *           Type of the node
    * @return List with nodes
    */
   public List<Node> getNodes(Class<?> type) {
      List<Node> result = new ArrayList<Node>();

      for (Node n : this.nodes) {
         if (type.isInstance(n))
            result.add(n);
      }

      return result;
   }

   /**
    * Get all edges
    * 
    * @return List with edges
    */
   public List<Edge> getEdges() {
      return this.edges;
   }

   /**
    * Get edges of a certain type
    * 
    * @param type
    *           Type
    * @return List with edges
    */
   public List<Edge> getEdges(EdgeType type) {
      List<Edge> result = new ArrayList<Edge>();
      for (Edge e : this.edges)
         if (e.getEdgeType() == type)
            result.add(e);
      return result;
   }

   /**
    * Get all edges
    * 
    * @return List with edges
    */
   public List<Edge> getEdgesRecursively() {
      List<Edge> result = new ArrayList<Edge>();
      List<CompositeNode<?, ?>> nodesToCheck = new ArrayList<>();

      for (Node n : this.nodes)
         if (n instanceof CompositeNode<?, ?>)
            nodesToCheck.add((CompositeNode<?, ?>) n);

      for (int i = 0; i < nodesToCheck.size(); i++) {
         Node n = nodesToCheck.get(i);
         if (n instanceof Partition) {
            // Add sub nodes
            for (Node subNode : ((Partition) n).getInnerGraph().getNodes())
               if (subNode instanceof CompositeNode<?, ?>)
                  nodesToCheck.add((CompositeNode<?, ?>) n);

            // Add edges
            for (Edge e : ((Partition) n).getInnerGraph().getEdges())
               result.add(e);
         } else if (n instanceof BranchedConstruct<?, ?>) {
            // Add sub nodes
            for (Graph sg : ((BranchedConstruct<?, ?>) n).getBranches()) {
               if (sg != null) {
                  for (Node subNode : sg.getNodes())
                     if (subNode instanceof CompositeNode<?, ?>)
                        nodesToCheck.add((CompositeNode<?, ?>) n);

                  // Add edges
                  result.addAll(sg.getEdges());
               }
            }
         } else if (n instanceof LoopConstruct) {
            // Add sub nodes
            for (Node subNode : ((LoopConstruct) n).getInnerGraph().getNodes())
               if (subNode instanceof CompositeNode<?, ?>)
                  nodesToCheck.add((CompositeNode<?, ?>) n);

            // Add edges
            result.addAll(((LoopConstruct) n).getInnerGraph().getEdges());
         } else {
            System.out.println("error, unkown node type found");
         }
      }

      result.addAll(this.edges);
      return result;
   }

   /**
    * Get the incoming edges from a certain node in the graph
    * 
    * @param node
    *           Node
    * @param types
    *           Type of the edges
    * @return Incoming edges
    */
   public List<Edge> getIncomingEdges(Node node, EdgeType... types) {
      List<Edge> result = new ArrayList<Edge>();

      for (Edge e : this.edges) {
         if (e.getEnd() == node) {
            if (types.length == 0)
               result.add(e);
            else {
               for (EdgeType t : types) {
                  if (t == e.getEdgeType())
                     result.add(e);
               }
            }
         }
      }
      return result;
   }
   
   public List<Edge> getIncomingEdgesRecursively(Node node, EdgeType... types) {
      List<Edge> result = new ArrayList<Edge>();

      graphLoop:
      for(Graph p : getAllGraphsAndSubGraphs())
         for (Edge e : p.getEdges()) {
            if (e.getStart() == node) {
               if (types.length == 0)
                  result.add(e);
               else {
                  for (EdgeType t : types) {
                     if (t == e.getEdgeType())
                        result.add(e);
                  }
               }
               break graphLoop;
            }
         }
      return result;
   }

   /**
    * Get the outgoing edges of a certain node
    * 
    * @param node
    *           Node
    * @param types
    *           Type of the edges
    * @return List with outgoing edges
    */
   public List<Edge> getOutgoingEdges(Node node, EdgeType... types) {
      List<Edge> result = new ArrayList<Edge>();

      for (Edge e : this.edges) {
         if (e.getStart() == node) {
            if (types.length == 0)
               result.add(e);
            else {
               for (EdgeType t : types) {
                  if (t == e.getEdgeType())
                     result.add(e);
               }
            }
         }
      }
      return result;
   }

   public List<Edge> getOutgoingEdgesRecursively(Node node, EdgeType... types) {
      List<Edge> result = new ArrayList<Edge>();

      graphLoop:
      for(Graph p : getAllGraphsAndSubGraphs())
         for (Edge e : p.getEdges()) {
            if (e.getEnd() == node) {
               if (types.length == 0)
                  result.add(e);
               else {
                  for (EdgeType t : types) {
                     if (t == e.getEdgeType())
                        result.add(e);
                  }
               }
               
               break graphLoop;
            }
         }
      return result;
   }

   /**
    * Find an edge originating from a node and terminating in another node of a
    * certain type
    * 
    * @param start
    *           Start node
    * @param end
    *           End node
    * @param types
    *           Type
    * @return Specific edge
    */
   public Edge findEdge(Node start, Node end, EdgeType... types) {
      List<EdgeType> lTypes = Arrays.asList(types);
      for (Edge e : this.edges) {
         if (e.getStart() == start && e.getEnd() == end
               && (lTypes.size() == 0 || lTypes.contains(e.getEdgeType())))
            return e;
      }
      return null;
   }

   /**
    * Manually set the start node of the graph
    * 
    * @param startNode
    */
   public void setStartNode(Node startNode) {
      this.startNode = startNode;
   }

   /**
    * Get the start node in the graph.
    * 
    * @return Start node
    */
   public Node getStartNode() {
      return this.startNode;
   }

   /**
    * Get the end node in the graph
    * 
    * @return End node
    */
   public Node getEndNode() {
      for (Node n : this.nodes) {
         if (getIncomingEdges(n, EdgeType.Control, EdgeType.Communication).size() >= 0
               && getOutgoingEdges(n, EdgeType.Control, EdgeType.Communication).size() == 0)
            return n;
      }

      if (this.nodes.size() > 0)
         return this.nodes.get(this.nodes.size() - 1);

      return null;
   }

   private Node findStartNode() {
      for (Node n : this.nodes) {
         if (getIncomingEdges(n, EdgeType.Control).size() == 0
               && getOutgoingEdges(n, EdgeType.Control).size() >= 0)
            return n;
      }

      if (this.nodes.size() > 0)
         return this.nodes.get(0);

      return null;
   }

   public HashSet<Graph> getAllGraphsAndSubGraphs() {
      HashSet<Graph> result = new HashSet<Graph>();

      if (this.getNodes().size() > 0)
         result.add(this);

      for (Node n : this.getNodes()) {
         if (n instanceof BranchedConstruct<?, ?>) {
            for (Graph branch : ((BranchedConstruct<?, ?>) n).getBranches()) {
               if (branch != null)
                  for (Graph subResult : branch.getAllGraphsAndSubGraphs())
                     result.add(subResult);
            }
         } else if (n instanceof Partition) {
            result.addAll((((Partition) n).getInnerGraph())
                  .getAllGraphsAndSubGraphs());
         } else if (n instanceof LoopConstruct) {
            result.addAll((((LoopConstruct) n).getInnerGraph())
                  .getAllGraphsAndSubGraphs());
         }
      }

      return result;
   }

   @Override
   public String toString() {
      return toString(false);
   }

   /**
    * Create simple string representation of the graph
    */
   public String toString(boolean detailedView) {
      String result = "{Graph: [nodes: ";

      for (int i = 0; i < this.nodes.size(); i++) {
         result += nodes.get(i).getName();
         if (detailedView)
            result += "(" + nodes.get(i).getClass().toString() + ")";
         if (i != nodes.size() - 1)
            result += ", ";
      }

      result += "], [edges: ";

      for (int i = 0; i < this.edges.size(); i++) {
         Edge e = this.edges.get(i);
         result += "(" + e.getStart().getName() + ","
               + e.getEdgeType().toString() + "," + e.getEnd().getName() + ")";
         if (i != edges.size() - 1)
            result += ", ";
      }

      result += "]}";

      return result;
   }

   /**
    * Add the nodes and edges of the newGraph to the end of the lists of nodes
    * and edges of this graph. Whether the node list is not empty a new control
    * edge will be created between the end node of this graph and the start node
    * of the newGraph.
    * 
    * @param newGraph
    *           - The graph to add. If the node list is empty, nothing will
    *           happen.
    * @author Lucas Venezian Povoa
    */
   public void merge(Graph newGraph) {
      if (!newGraph.getNodes().isEmpty()) {
         if (!this.nodes.isEmpty())
            this.edges.add(new Edge(this.getEndNode(), newGraph.getStartNode(),
                  EdgeType.Control));

         else
            this.startNode = newGraph.getStartNode();

         this.nodes.addAll(newGraph.getNodes());
         this.edges.addAll(newGraph.getEdges());
      }
   }

   public void addAttribute(String name, Object value) {
      this.attributes.put(name, value);
   }
   
   public boolean hasAttribute(String name) {
      return this.attributes.containsKey(name);
   }
   
   public HashMap<String,Object> getAttributes() {
      return this.attributes;
   }
   
   public List<Node> getNodesInWorkflowSequence() {
      List<Node> result = new ArrayList<Node>();
      
      Node tmp = getStartNode();
      
      while(tmp != null) {
         try {
            result.add(tmp);
            
            tmp = getOutgoingEdges(
                  tmp, EdgeType.Control)
                  .get(0).getEnd();
         }
         catch(IndexOutOfBoundsException e) {
            tmp = null;
         }
      }
      
      return result;
   }
}
